#include <iostream>
using namespace std;

struct node
{
	int val;
	node *next;
	node(int v, node *nt)
	{
		val = v;
		next = nt;
	}
};

void reverselist(node **head)
{
	node *pre = NULL;
	node *cur = *head;
	while(cur)
	{
		node* next = cur->next;
		cur->next = pre;
		pre = cur;
		cur = next;
	}
	*head = pre;
}

node* reverselist_r(node *head)
{
	if(!head || !head->next)
		return head;
	node *new_head = reverselist_r(head->next);
	head->next->next = head;
	head->next = NULL;
	return new_head;
}

void printlist(node *head)
{
	while(head)
	{
		cout << head->val << " ";
		head = head->next;
	}
	cout << endl;
}

int main()
{
	node n4(4, NULL);
	node n3(3, &n4);
	node n2(2, &n3);
	node n1(1, &n2);
	node *head = &n1;	
	printlist(head);	
	reverselist(&head);
	printlist(head);	
	node *rew_head = reverselist_r(head);
	printlist(rew_head);
	return 0;
}
